//===- AADriver.cpp - Driver for Alias Analysis" --------------------------===//
//
//	Copyright (C) 2014	Victor Hugo Sperle Campos
//						George Souza Oliveira
//				
//
//===----------------------------------------------------------------------===//

#include "AADriver.h"

using namespace llvm;

void DisjointSets::make_set(Value* p)
{
	SetVector<Value*> s;
	s.insert(p);

	this->sets.push_back(s);
}

int DisjointSets::find_set(Value* p)
{
	int i, n = this->sets.size();

	for (i = 0; i < n; ++i) {
		const SetVector<Value*>& set = sets[i];

		if (set.count(p))
			return i;
	}

	return -1;
}

void DisjointSets::union_sets(unsigned i, unsigned j)
{
	if (i == j)
		return;

	if (i >= sets.size() or j >= sets.size())
		return;

	// Add j set to i
	sets[i].insert(sets[j].begin(), sets[j].end());

	// Remove j
	SmallVector<SetVector<Value*>, 16>::iterator it = sets.begin();
	for (unsigned k = 0; k < j; k++)
		it++;

	assert(it != sets.end());

	sets.erase(it);
}

bool AADriver::runOnModule(Module &M)
{

	// Fetch Alias Analysis information
	AliasAnalysis& AA = getAnalysis<AliasAnalysis>();

	this->DS = new DisjointSets();

	SetVector<Value *> Pointers;

	for (Module::iterator Mit = M.begin(), Mend = M.end(); Mit != Mend; ++Mit) {
		Function& F = *Mit;

		for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E;
				++I)
			if (I->getType()->isPointerTy()) { // Add all pointer arguments.
				Pointers.insert(I);
			}

		for (Function::iterator Fit = F.begin(), Fend = F.end(); Fit != Fend;
				++Fit) {
			for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E;
					++I) {
				if (I->getType()->isPointerTy()) // Add all pointer instructions.
					Pointers.insert(&*I);

				Instruction &Inst = *I;
				// Consider all operands.
				for (Instruction::op_iterator OI = Inst.op_begin(), OE =
						Inst.op_end(); OI != OE; ++OI)
					if (isInterestingPointer(*OI)) {
						Pointers.insert(*OI);
					}
			}
		}

		for (SetVector<Value *>::iterator I1 = Pointers.begin(), E =
				Pointers.end(); I1 != E; ++I1) {
			errs() << **I1 << "\n";
			DS->make_set(*I1);
		}

		// iterate over the worklist, and run the full (n^2)/2 disambiguations
		for (SetVector<Value *>::iterator I1 = Pointers.begin(), E =
				Pointers.end(); I1 != E; ++I1) {
			uint64_t I1Size = AliasAnalysis::UnknownSize;
			Type *I1ElTy =
					cast<PointerType>((*I1)->getType())->getElementType();
			if (I1ElTy->isSized())
				I1Size = AA.getTypeStoreSize(I1ElTy);

			for (SetVector<Value *>::iterator I2 = Pointers.begin(); I2 != I1;
					++I2) {
				uint64_t I2Size = AliasAnalysis::UnknownSize;
				Type *I2ElTy =
						cast<PointerType>((*I2)->getType())->getElementType();
				if (I2ElTy->isSized())
					I2Size = AA.getTypeStoreSize(I2ElTy);

				int i1, i2;

				switch (AA.alias(*I1, I1Size, *I2, I2Size))
				{
					case AliasAnalysis::NoAlias:
					case AliasAnalysis::PartialAlias:
						break;
					case AliasAnalysis::MayAlias:
					case AliasAnalysis::MustAlias:
						i1 = DS->find_set(*I1);
						i2 = DS->find_set(*I2);

						errs() << "Buscas por \n" << **I1 << "\n" << **I2 << "\n\n";

						if (i1 != -1 and i2 != -1) {
							DS->union_sets(i1, i2);
						}

						for (SmallVector<SetVector<Value*>, 16>::const_iterator
								vit = DS->sets.begin(), vend = DS->sets.end();
								vit != vend; ++vit) {
							const SetVector<Value*>& set = *vit;

							errs() << "{";
							for (SetVector<Value*>::const_iterator sit =
									set.begin(), send = set.end(); sit != send;
									++sit) {
								Value* p = *sit;

								errs() << p->getName() << ", ";
							}
							errs() << "}\n";
						}
						errs() << "\n\n";
						break;
				}
			}
		}

	}

	for (SmallVector<SetVector<Value*>, 16>::const_iterator vit =
			DS->sets.begin(), vend = DS->sets.end(); vit != vend; ++vit) {
		const SetVector<Value*>& set = *vit;

		errs() << "{";
		for (SetVector<Value*>::const_iterator sit = set.begin(), send =
				set.end(); sit != send; ++sit) {
			Value* p = *sit;

			errs() << p->getName() << ", ";
		}
		errs() << "}\n";
	}

	return false;
}

void AADriver::getAnalysisUsage(AnalysisUsage &AU) const
{
	AU.addRequiredTransitive<AliasAnalysis>();
	AU.setPreservesAll();
}

char AADriver::ID = 0;
static RegisterPass<AADriver> Y("aadriver",
		"AADriver World Pass (with getAnalysisUsage implemented)", false,
		false);
